home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 244_01 / three31.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-24  |  8.3 KB  |  321 lines
  1.  
  2. /* program to analyze the de Bruijn diagram of a cellular */
  3. /* automaton and report all the periodic states. */
  4. /* version for totalistic (3,1), third generation */
  5. /* [Harold V. McIntosh, 4 May 1987] */
  6.  
  7. # include <stdio.h>
  8.  
  9. # define MC     8                /* maximum number of columns */
  10. # define NS      7                /* number of distinct sums */
  11. # define ML    24                /* pause after so many lines */
  12.  
  13. char arry[3][3][3][3][3][3][3];
  14. int  rule[NS];
  15. int  nc, nl;
  16.  
  17. main() {
  18. int i;
  19.  
  20. printf("Rule number:\n");
  21. printf("0..1..2\n");
  22. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  23.  
  24. nc=0;
  25. nl=0;
  26.  
  27. printf("\n - several minutes may elapse for each case - \n");
  28.  
  29. kwait(0); printf("Strings conforming to (3,0):"); kwait(0);
  30. pass1a();
  31. pass2i();
  32. pass2o();
  33. pass4();
  34.  
  35. kwait(0); printf("Strings conforming to (3,1):"); kwait(0);
  36. pass1b();
  37. pass2i();
  38. pass2o();
  39. pass4();
  40.  
  41. kwait(0); printf("Strings conforming to (3,2):"); kwait(0);
  42. pass1c();
  43. pass2i();
  44. pass2o();
  45. pass4();
  46.  
  47. kwait(0); printf("Strings conforming to (3,3):"); kwait(0);
  48. pass1d();
  49. pass2i();
  50. pass2o();
  51. pass4();
  52.  
  53. } /* end of main */
  54.  
  55. pass1a() {            /* mark sequences conforming to (3,0) */
  56. int i0, i1, i2, i3, i4, i5, i6;
  57. int j0, j1, j2, j3, j4;
  58. int i, j, k;
  59. printf(" pass1a\015");
  60. for (i0=0; i0<3; i0++) {
  61. for (i1=0; i1<3; i1++) {
  62. for (i2=0; i2<3; i2++) {
  63. for (i3=0; i3<3; i3++) {
  64. for (i4=0; i4<3; i4++) {
  65. for (i5=0; i5<3; i5++) {
  66. for (i6=0; i6<3; i6++) {
  67. j0=rule[i0+i1+i2];
  68. j1=rule[i1+i2+i3];
  69. j2=rule[i2+i3+i4];
  70. j3=rule[i3+i4+i5];
  71. j4=rule[i4+i5+i6];
  72. i=rule[j0+j1+j2];
  73. j=rule[j1+j2+j3];
  74. k=rule[j2+j3+j4];
  75. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i3?'Y':'N';
  76. };};};};};};};
  77. }
  78.  
  79. pass1b() {            /* mark sequences conforming to (3,1) */
  80. int i0, i1, i2, i3, i4, i5, i6;
  81. int j0, j1, j2, j3, j4;
  82. int  i, j, k;
  83. printf(" pass1b\015");
  84. for (i0=0; i0<3; i0++) {
  85. for (i1=0; i1<3; i1++) {
  86. for (i2=0; i2<3; i2++) {
  87. for (i3=0; i3<3; i3++) {
  88. for (i4=0; i4<3; i4++) {
  89. for (i5=0; i5<3; i5++) {
  90. for (i6=0; i6<3; i6++) {
  91. j0=rule[i0+i1+i2];
  92. j1=rule[i1+i2+i3];
  93. j2=rule[i2+i3+i4];
  94. j3=rule[i3+i4+i5];
  95. j4=rule[i4+i5+i6];
  96. i=rule[j0+j1+j2];
  97. j=rule[j1+j2+j3];
  98. k=rule[j2+j3+j4];
  99. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i2?'Y':'N';
  100. };};};};};};};
  101. }
  102.  
  103. pass1c() {            /* mark sequences conforming to (3,2) */
  104. int i0, i1, i2, i3, i4, i5, i6;
  105. int j0, j1, j2, j3, j4;
  106. int i, j, k;
  107. printf(" pass1c\015");
  108. for (i0=0; i0<3; i0++) {
  109. for (i1=0; i1<3; i1++) {
  110. for (i2=0; i2<3; i2++) {
  111. for (i3=0; i3<3; i3++) {
  112. for (i4=0; i4<3; i4++) {
  113. for (i5=0; i5<3; i5++) {
  114. for (i6=0; i6<3; i6++) {
  115. j0=rule[i0+i1+i2];
  116. j1=rule[i1+i2+i3];
  117. j2=rule[i2+i3+i4];
  118. j3=rule[i3+i4+i5];
  119. j4=rule[i4+i5+i6];
  120. i=rule[j0+j1+j2];
  121. j=rule[j1+j2+j3];
  122. k=rule[j2+j3+j4];
  123. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i1?'Y':'N';
  124. };};};};};};};
  125. }
  126.  
  127. pass1d() {            /* mark sequences conforming to (3,3) */
  128. int i0, i1, i2, i3, i4, i5, i6;
  129. int j0, j1, j2, j3, j4;
  130. int i, j, k;
  131. printf(" pass1d\015");
  132. for (i0=0; i0<3; i0++) {
  133. for (i1=0; i1<3; i1++) {
  134. for (i2=0; i2<3; i2++) {
  135. for (i3=0; i3<3; i3++) {
  136. for (i4=0; i4<3; i4++) {
  137. for (i5=0; i5<3; i5++) {
  138. for (i6=0; i6<3; i6++) {
  139. j0=rule[i0+i1+i2];
  140. j1=rule[i1+i2+i3];
  141. j2=rule[i2+i3+i4];
  142. j3=rule[i3+i4+i5];
  143. j4=rule[i4+i5+i6];
  144. i=rule[j0+j1+j2];
  145. j=rule[j1+j2+j3];
  146. k=rule[j2+j3+j4];
  147. arry[i0][i1][i2][i3][i4][i5][i6]=rule[i+j+k]==i0?'Y':'N';
  148. };};};};};};};
  149. }
  150.  
  151. /* Pass2i flags links which have an incoming arrow */
  152. pass2i() {int i0, i1, i2, i3, i4, i5, i6, m;
  153. do {
  154. printf(" pass2i\015");
  155. for (i0=0; i0<3; i0++) {
  156. for (i1=0; i1<3; i1++) {
  157. for (i2=0; i2<3; i2++) {
  158. for (i3=0; i3<3; i3++) {
  159. for (i4=0; i4<3; i4++) {
  160. for (i5=0; i5<3; i5++) {
  161. for (i6=0; i6<3; i6++) {
  162. if ((arry[i0][i1][i2][i3][i4][i5][i6]&0x5F)=='Y')
  163.  {for (m=0; m<3; m++) arry[i1][i2][i3][i4][i5][i6][m]|=0x20;};
  164. };};};};};};};
  165. } while (pass3()!=0); }
  166.  
  167. /* Pass2o flags links which have an outgoing arrow */
  168. pass2o() {int i0, i1, i2, i3, i4, i5, i6, m;
  169. do {
  170. printf(" pass2o\015");
  171. for (i0=0; i0<3; i0++) {
  172. for (i1=0; i1<3; i1++) {
  173. for (i2=0; i2<3; i2++) {
  174. for (i3=0; i3<3; i3++) {
  175. for (i4=0; i4<3; i4++) {
  176. for (i5=0; i5<3; i5++) {
  177. for (i6=0; i6<3; i6++) {
  178. if ((arry[i0][i1][i2][i3][i4][i5][i6]&0x5F)=='Y')
  179.  {for (m=0; m<3; m++) arry[m][i0][i1][i2][i3][i4][i5]|=0x20;};
  180. };};};};};};};
  181. } while (pass3()!=0); }
  182.  
  183. /*  erase flags, mark survivors, count channges */
  184. int pass3() {int i0, i1, i2, i3, i4, i5, i6, l;
  185. l=0;
  186. printf(" pass3 \015");
  187. for (i0=0; i0<3; i0++) {
  188. for (i1=0; i1<3; i1++) {
  189. for (i2=0; i2<3; i2++) {
  190. for (i3=0; i3<3; i3++) {
  191. for (i4=0; i4<3; i4++) {
  192. for (i5=0; i5<3; i5++) {
  193. for (i6=0; i6<3; i6++) {
  194. switch (arry[i0][i1][i2][i3][i4][i5][i6]) {
  195.     case 'y': arry[i0][i1][i2][i3][i4][i5][i6]='Y'; break;
  196.     case 'Y': arry[i0][i1][i2][i3][i4][i5][i6]='N'; l=1; break;
  197.     case 'n': case 'N': arry[i0][i1][i2][i3][i4][i5][i6]='N'; break;
  198.     default: break; };
  199. };};};};};};};
  200. return l; }
  201.  
  202. /* pass4 - print loops which remain */
  203. pass4() {
  204. int i0, i1, i2, i3, i4, i5, i6;
  205. int j0, j1, j2, j3, j4, j5, j6;
  206. int  k, l, m;
  207. printf(" pass4 \015");
  208. for (i0=0; i0<3; i0++) {
  209. for (i1=0; i1<3; i1++) {
  210. for (i2=0; i2<3; i2++) {
  211. for (i3=0; i3<3; i3++) {
  212. for (i4=0; i4<3; i4++) {
  213. for (i5=0; i5<3; i5++) {
  214. for (i6=0; i6<3; i6++) {
  215. j1=i1; j2=i2; j3=i3; j4=i4; j5=i5; j6=i6;
  216. l=0;
  217. m=0;
  218. do {
  219.         if (arry[0][j1][j2][j3][j4][j5][j6]=='Y')
  220.     {arry[0][j1][j2][j3][j4][j5][j6]='y';
  221.     k=j6; j6=j5; j5=j4; j4=j3; j3=j2; j2=j1; j1=0; m=1;}
  222.   else {if (arry[1][j1][j2][j3][j4][j5][j6]=='Y')
  223.     {arry[1][j1][j2][j3][j4][j5][j6]='y';
  224.     k=j6; j6=j5; j5=j4; j4=j3; j3=j2; j2=j1; j1=1; m=1;}
  225.   else {if (arry[2][j1][j2][j3][j4][j5][j6]=='Y')
  226.     {arry[2][j1][j2][j3][j4][j5][j6]='y';
  227.     k=j6; j6=j5; j5=j4; j4=j3; j3=j2; j2=j1; j1=2; m=1;}
  228.   else {l=1;
  229.     if (m==1) {j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=k;};
  230.     };};};
  231.   } while (l==0);
  232. l=0; 
  233. m=0;
  234. do {
  235.         if (arry[j0][j1][j2][j3][j4][j5][0]=='y')
  236.    {prf(j0,j1,j2,j3,j4,j5,0);
  237.    arry[j0][j1][j2][j3][j4][j5][0]='N';
  238.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=0; m=1;}
  239.   else {if (arry[j0][j1][j2][j3][j4][j5][1]=='y')
  240.    {prf(j0,j1,j2,j3,j4,j5,1);
  241.    arry[j0][j1][j2][j3][j4][j5][1]='N';
  242.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=1; m=1;}
  243.   else {if (arry[j0][j1][j2][j3][j4][j5][2]=='y')
  244.    {prf(j0,j1,j2,j3,j4,j5,2);
  245.    arry[j0][j1][j2][j3][j4][j5][2]='N';
  246.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=2; m=1;}
  247.   else {l=1;};};};
  248.   } while (l==0);
  249. l=0;
  250. do {
  251.         if (arry[j0][j1][j2][j3][j4][j5][0]=='Y')
  252.    {prf(j0,j1,j2,j3,j4,j5,0);
  253.    arry[j0][j1][j2][j3][j4][j5][0]='N';
  254.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=0; m=1;}
  255.   else {if (arry[j0][j1][j2][j3][j4][j5][1]=='Y')
  256.    {prf(j0,j1,j2,j3,j4,j5,1);
  257.    arry[j0][j1][j2][j3][j4][j5][1]='N';
  258.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=1; m=1;}
  259.   else {if (arry[j0][j1][j2][j3][j4][j5][2]=='Y')
  260.    {prf(j0,j1,j2,j3,j4,j5,2);
  261.    arry[j0][j1][j2][j3][j4][j5][2]='N';
  262.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=2; m=1;}
  263.   else {l=1; if (m==1) kwait(0);};};};
  264.   } while (l==0);
  265. };};};};};};};
  266. }
  267.  
  268. /* print one of the individual links in a chain */
  269. prf(i0,i1,i2,i3,i4,i5,i6)
  270. int i0, i1, i2, i3, i4, i5, i6; {
  271. kwait(1);
  272. printf("%1d",i0);
  273. printf("%1d",i1);
  274. printf("%1d",i2);
  275. printf("%1d",i3);
  276. printf("%1d",i4);
  277. printf("%1d",i5);
  278. printf("-");
  279. printf("%1d",i6);
  280. printf(" ");}
  281.  
  282. /* print the whole list of links - impractical except for debugging  */
  283. pall() {
  284. int i0, i1, i2, i3, i4, i5, i6;
  285. for (i0=0; i0<3; i0++) {
  286. for (i1=0; i1<3; i1++) {
  287. for (i2=0; i2<3; i2++) {
  288. for (i3=0; i3<3; i3++) {
  289. for (i4=0; i4<3; i4++) {
  290. for (i5=0; i5<3; i5++) {
  291. for (i6=0; i6<3; i6++) {
  292. printf("%c",arry[i0][i1][i2][i3][i4][i5][i6]);
  293. };};};};};};};
  294. printf("\n");
  295. }
  296.  
  297. /* keyboard status */
  298. kbdst() {return bdos(11)&0xFF;}
  299.  
  300. /* direct keyboard input, no echo */
  301. kbdin() {int c;
  302. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  303. return c;}
  304.  
  305. /* pause at the end of a full screen */
  306. kwait(i) int i; {
  307. switch (i) {
  308.   case 0: printf("\n"); nc=0; nl++; break;
  309.   case 1: {if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++;}; break;
  310.   default: break;};
  311. if (nl==ML) {
  312.   nl=0;
  313.   printf(" press any key to continue\015");
  314.   while (kbdst()) {};
  315.   kbdin();
  316.   printf("-                         \n");
  317.   };
  318. }
  319.  
  320. /* end */
  321.